FLOW6 最长不下降子序列问题

模型：

最多不相交路径->网络最大流

题意：

给定正整数序列$x_1 \sim x_n$ ， 计算其最长不下降子序列的长度 $s$。 计算从给定的序列中最多可取出多少个长度为 $s$ 的不下降子序列。 如果允许在取出的序列中多次使用 $x_1$ 和 $x_n$ ，则从给定序列中最多可取出多少个长度为 $s$ 的不下降子序列。

题解：

将“与之关联的不下降子序列的数量”看成本问题中的“流”

自然的，先拆点，拆成出点和入点

Q1：

第一问设f[i]表示以i结尾的最长不下降子序列的长度，$O(n^2)$DP，轻松解决

设此问答案为ans1

Q2：

第二问采用网络最大流

因为一个点只能有一次出入，所以此问中的所有边的容量都是为1的

首先，常规操作，在每个点内部（也就是从入点向出点）连边

考虑水流的源点，其f[i]必然是等于ans1的，于是从超级源点向所有源点连边

考虑水流的汇点，其f[i]必然是等于1的，于是从所有汇点向超级汇点连边

考虑水流的存在需满足的要求，对于可以存在水流的点i和j(i<j)，$f[i]+1==f[j]$且$a[i]<=a[j]$，然后对于所有的i,j关系连边

跑一遍最大流，即可得出ans2

Q3：

因为1和n能用多次，所以在Q2网络图的基础上将与1或n相关联的边的容量修改为inf

重新跑一遍最大流，即可得出ans3

注意特判ans1==1的情况

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

const int oo=0x3f3f3f3f;
const int N=1050,M=3e3+5;
int en=1,h[N],d[N],n,m,s,t,use,cur[N],ans,ma,ans1,ans2,ans3,f[N],a[N];
bool v[N];

struct edge{
    int n,v,f;
}e[N+M<<1];

void add(int x,int y,int z){
    e[++en]=(edge){h[x],y,z};
    h[x]=en;
}

void exadd(int x,int y,int z){
    add(x,y,z);
    add(y,x,0);
}

bool bfs(int s,int aim){
    memset(d,0,sizeof d);
    memcpy(cur,h,sizeof cur);
    queue<int> q;
    q.push(s);
    d[s]=1;
    while(!q.empty()){
        int x=q.front();
        q.pop();
        for(int i=h[x];i;i=e[i].n){
            int y=e[i].v;
            if(d[y]==0&&e[i].f){
                d[y]=d[x]+1;
                if(y==aim) return 1;
                q.push(y);
            }
        }
    }
    return 0;
}

int dfs(int x,int flow,int aim){
    if(x==aim) return flow;
    int rest=flow;
    for(int &i=cur[x];i&&rest;i=e[i].n){
        int y=e[i].v;
        if(d[y]==d[x]+1&&e[i].f){
            int flow=dfs(y,min(rest,e[i].f),aim);
            rest-=flow;
            e[i].f-=flow;
            e[i^1].f+=flow;
        }
    }
    return flow-rest;
}

int dinic(int s,int t){
    int res=0;
    while(bfs(s,t)) res+=dfs(s,oo,t);
    return res;
}

signed main(){
    read(n);
    s=1,t=n+n+2;
    for(int i=1;i<=n;i++){
        read(a[i]);
        f[i]=1;
        for(int j=1;j<i;j++) if(a[j]<=a[i])
            f[i]=max(f[i],f[j]+1);
        ans1=max(ans1,f[i]);
    }
    if(ans1==1){
        write(1);puts("");
        write(n);puts("");
        write(n);
        return 0;
    }
    for(int i=1;i<=n;i++){
        exadd(i+s,i+s+n,1);
        if(f[i]==1) exadd(s,i+s,1);
        if(f[i]==ans1) exadd(i+s+n,t,1);
        for(int j=i+1;j<=n;j++) if(f[j]==f[i]+1&&a[j]>=a[i])
            exadd(i+s+n,j+s,1);
    }
    ans2=dinic(s,t);
    exadd(1+s,1+s+n,oo);
    exadd(s,1+s,oo);
    for(int i=2;i<=en;i+=2) e[i].f+=e[i^1].f,e[i^1].f=0;
    if(f[n]==ans1){
        exadd(n+s,n+s+n,oo);
        exadd(n+s+n,t,oo);
    }
    ans3=dinic(s,t);
    write(ans1);puts("");
    write(ans2);puts("");
    write(ans3);
}